'''
地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。
例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？


解题思路：递归回溯 笨方法
1、递归参数传入当前坐标点
2、计算在当前坐标点满足条件的点集合，将满足条件的点集合存入栈中
3、再遍历点集合中的元素作为新的当前坐标点进行递归
4、最后返回栈中元素个数
'''
class Solution:
    def movingCount(self, threshold, rows, cols):
        if threshold < 0:return 0
        self.sites = [(0,0)]
        # visit递归用于查找到满足条件的下一点放入栈中
        self.visit((0,0),threshold, rows, cols)
        return len(self.sites)
    def visit(self,site,threshold, rows, cols):
        x, y = site
        # 筛选出满足约束条件的下一点集合并填入到栈中
        sets = [(i, j) for i, j in [(x+1,y),(x,y+1),(x-1,y),(x,y-1)]
               if 0<=i<rows and 0<=j<cols and (i,j) not in self.sites and (self.numSum(i)+self.numSum(j)) <= threshold]
        self.sites += sets
        # 若没有满足条件的下一点返回空
        if not sets: return
        # 若存在则继续查找递归
        for s in sets:
            self.visit(s,threshold,rows,cols)
    # 计算坐标点和
    def numSum(self, num):
        sums = 0
        while num>0:
            sums += num % 10
            num = num//10
        return sums

s = Solution()
print(s.movingCount(5,10,10))
# print(s.numSum(14))